package com.likou;

import java.util.HashMap;
import java.util.Map;

public class q169 {

    // 摩尔投票法
    public int majorityElement(int[] nums) {
        int res = 0;
        int count = 0;
        for (int num : nums) {
            if (count == 0) {
                res = num;
            }

            if (res == num) {
                count++;
            } else {
                count--;
            }
        }

        return res;
    }

//    public int majorityElement(int[] nums) {
//        int ans = 0;
//        Map<Integer, Integer> map = new HashMap<>();
//        int n = nums.length;
//
//        for (int i = 0; i < n; i++) {
//            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
//            if (map.get(nums[i]) > n / 2) {
//                ans = nums[i];
//                break;
//            }
//        }
//
//        return ans;
//    }
}
